The present invention relates to data communication switching and, more particularly, to methods and devices for assisting the copying of packets for multicasting.
Data communication switches receive packets on ingress ports, format them for the xe2x80x9cnext hopxe2x80x9d, and transmit them on egress ports en route to their ultimate destinations. When more than one ultimate destination is indicated, i.e., the packet requires multicasting, the switch must generally make multiple copies of the packet or a portion thereof and prepends each of the copies with a different outbound header. Conventional switches have relied heavily on software-driven central processing units (CPUs) to accomplish the required copying. Such CPU reliance has introduced intervening steps into the switching process which have caused latency and imposed additional buffering requirements. Overall switching performance has suffered as a result. Therefore, there is a general need for methods and devices for more efficiently processing packets requiring multicasting in data communication switches, and a more particular need for a hardware-based solution to the task of multicast copying.
In its most basic feature, the present invention provides a hardware copy assist for facilitating data communication switch multicasting.
In one aspect of the invention, packets are copied in hardware in a quantity required to meet multicasting needs. This inventive aspect is achieved by storing packets in a switch queue and retaining a home mark to which a read address is reset when additional copying is indicated. Inbound packets are stored in the switch queue pending resolution of forwarding requirements. A home mark is always set to the first-written address of the packet at the head of the queue. If additional copying of the packet is indicated, the read address is reset to the home mark after the most recent copy of the packet is delivered. If additional copying is not indicated, the home mark is advanced to the first-written address for the next packet for copying from the switch queue after the most recent copy is delivered.
In another aspect of the invention, the home mark is used in a watermark check to guarantee that the packet at the head of the queue is not overwritten before the required number of copies has been made. This inventive aspect is achieved by using the differential between the write address and the home mark (rather than the current read address) as the benchmark of current queue fullness in a watermark check wherein the decision is made whether to grant queuing clearance to the next inbound data. By relying on the write address/home mark differential (rather than the write address/read address differential) in the watermark check, the addresses in which the packet at the head of the queue are stored are placed off-limits to the next inbound packet until it is certain that additional copying of the packet at the head of the queue will not be required.
In a preferred embodiment of the invention, the hardware copy assist is implemented with minimal switching overhead by making copying decisions incidental to the retrieval of outbound headers. Outbound headers are preferably retrieved by indexing a header table wherein all outbound headers for the same packet are stored as a linked list of entries. A check is made of each entry as the linked list is xe2x80x9cwalked-downxe2x80x9d to determine if there is another entry in the linked list, as indicated by the presence of a valid xe2x80x9cnext entryxe2x80x9d index. If there is a valid xe2x80x9cnext entryxe2x80x9d index, the read address is reset to the home mark after the most recent copy of the packet is delivered. If there is not a valid xe2x80x9cnext entryxe2x80x9d index, however, the home mark is advanced to the read address after the most recent copy of the packet is delivered.
These and other aspects of the present invention may be better understood by reference to the following detailed description taken in conjunction with the accompanying drawings which are briefly described below. Of course, the actual scope of the invention is defined by the appended claims.